UVA12177 First Knight

设 $dp(i,j)$ 表示由 $(i,j)$ 走到 $(n,m)$ 的期望步数。

那么显然有转移：

$dp(i,j)=1+(up(i,j) \times dp(i+1,j) + down(i,j) \times dp(i-1,j) + left(i,j) \times dp(i,j-1) + right(i,j) \times dp(i,j+1))$

其中 $up,down,left,right$ 分别表示 $(i,j)$ 向上/下/左/右走的概率。

边界条件： $dp(n,m)=0$

然后你发现它们互相有依赖，不能直接转移，所以直接高斯消元。

但这样时间复杂度是 $\mathcal O(n^3m^3)$，考虑优化

1. 因为每一个方程不为 $0$ 的系数最多 $5$ 个，所以增广矩阵其实很稀疏，系数为 $0$ 就不需要加减消元了。
2. 我们只需要 $dp(1,1)$ ，所以消成下三角矩阵就可以了。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define eps 1e-16

const int MAXN = 50;
int n , m , fn;
double a[ MAXN * MAXN + 5 ][ MAXN * MAXN + 5 ];

void Gauss( ) {
    for( int i = fn ; i >= 1 ; i -- ) {
        for( int j = i - 1 ; j >= 1 ; j -- ) {
            double t = a[ j ][ i ] / a[ i ][ i ];
            if( fabs( t ) < eps ) continue;
            for( int k = i ; k >= 1 ; k -- )
                a[ j ][ k ] -= t * a[ i ][ k ];
            a[ j ][ fn + 1 ] -= t * a[ i ][ fn + 1 ];
        }
    }
}

pair< int , int > dir[ 4 ] = { { 1 , 0 } , { 0 , 1 } , { -1 , 0 } , { 0 , -1 } };
double p[ MAXN + 5 ][ MAXN + 5 ][ 4 ];

int Hash( int x , int y ) {
    if( x < 1 || x > n || y < 1 || y > m ) return fn + 2; //越界
    return ( x - 1 ) * m + y;
}
int main( ) {
    while( scanf("%d %d",&n,&m) && ( n + m ) ) {
        fn = n * m;
        for( int k = 0 ; k < 4 ; k ++ )
            for( int i = 1 ; i <= n ; i ++ )
                for( int j = 1 ; j <= m ; j ++ )
                    scanf("%lf",&p[ i ][ j ][ k ]);
        memset( a , 0 , sizeof( a ) );
        for( int i = 1 ; i <= n ; i ++ )
            for( int j = 1 ; j <= m ; j ++ ) {
                int h = Hash( i , j );
                a[ h ][ h ] = -1;
                if( i == n && j == m ) continue;
                a[ h ][ fn + 1 ] = -1;
                for( int k = 0 ; k < 4 ; k ++ )
                    a[ h ][ Hash( i + dir[ k ].first , j + dir[ k ].second ) ] = p[ i ][ j ][ k ];
            }
        Gauss( );
        printf("%.1f\n", a[ 1 ][ fn + 1 ] / a[ 1 ][ 1 ] );
    }
    return 0;
}